\subsection{Minimum cost flow}
\begin{definition}
	A \textit{directed graph} (also known as a \textit{digraph}) \( G \) consists of a set of vertices and a set of edges; \( G = (V, E) \).
	The edges are such that \( E \subseteq V \times V \).
	Each edge \( (i,j) \) can be thought of as an edge pointing from vertex \( i \) to vertex \( j \).
	When \( E \) is symmetric (that is, \( (i,j) \in E \iff (j,i) \in E \)), we call \( G \) an \textit{undirected graph}.
\end{definition}
\begin{definition}
	Given a graph \( G = (V, E) \) on \( n \) vertices, we associate to every \( (i,j) \in E \) the number \( x_{ij} \).
	This represents the flow of a quantity from vertex \( i \) to vertex \( j \).
	The collection \( x \) of \( x_{ij} \) is called the \textit{flow}.
	The flow \( x \) is affected by
	\begin{enumerate}
		\item A vector \( \vb b \in \mathbb R^n \), where \( b_i \) is the amount of flow entering vertex \( i \) from outside the graph.
		      If \( b_i > 0 \), then vertex \( i \) is called a \textit{source}.
		      If \( b_i < 0 \), then vertex \( i \) is called a \textit{sink}.
		\item The cost matrix \( c \in \mathbb R^{n \times n} \), which gives the cost \( c_{ij} \) per unit of flow on \( (i,j) \in E \).
		      If the flow along \( (i,j) \) is \( x_{ij} \), the cost for this flow is \( c_{ij}x_{ij} \) (without the summation convention).
		\item The lower bound matrix \( \underline{M} \) and the upper bound matrix \( \overline{M} \), which give lower and upper bounds on \( x_{ij} \).
		      In particular, for all \( (i,j) \in E \), we require \( \underline m_{ij} \leq x_{ij} \leq \overline m_{ij} \).
	\end{enumerate}
\end{definition}
\begin{definition}
	The \textit{minimum cost flow} is the linear program
	\begin{alignat*}{2}
		 & \text{minimise}   & \qquad & \sum_{(i,j) \in E}c_{ij}x_{ij}                                                   \\
		 & \text{subject to} &        & \underline m_{ij} \leq x_{ij} \leq \overline m_{ij} \quad \forall (i,j) \in E    \\
		 &                   &        & b_i + \sum_{(j,i) \in E} x_{ji} = \sum_{(i,j)\in E} x_{ij} \quad \forall i \in V
	\end{alignat*}
	The second constraint is a conservation of flow equation.
	The amount of flow entering and leaving the vertex must be equal.
	Note that in order for the problem to be feasible, \( \sum b_i = 0 \); since the graph has no storage capacity at any vertex, the amount of flow that enters the graph must be the amount of flow that exits.
	Alternatively, we could prove this by finding the sum of the conservation of flow equations for all \( i \).
\end{definition}
\begin{definition}
	We can define the \textit{incidence matrix} \( A \colon \mathbb R^{\abs{V} \times \abs{E}} \).
	Each column of \( A \) is associated with an edge \( (i,j) \).
	We define that this column is filled with zeroes, except for \( +1 \) at position \( i \) and \( -1 \) at position \( j \).
	We can now rewrite the conservation of flow equation as
	\[
		A\vb x = \vb b
	\]
\end{definition}

\subsection{Transport problem}
The transport problem is a special case of the minimum cost flow problem.
Consider \( n \) suppliers, and \( m \) consumers.
Each supplier \( i \) has some capacity \( s_i \) for how much of this good they can satisfy,
and each consumer \( j \) has some demand \( d_j \) that they want to be fulfilled.
We will assume that there is exactly as much supply as demand; that is, \( \sum s_i = \sum d_j \).
The cost of transporting one unit of this good from supplier \( i \) to consumer \( j \) is \( c_{ij} \).
For this problem, the graph \( G \) is a \textit{bipartite graph}; it can be separated into a set of sources and a set of sinks, and the edges are only from the sources to the sinks.
The optimisation problem is
\begin{alignat*}{2}
	 & \text{minimise}   & \qquad & \sum_{i = 1}^n \sum_{j = 1}^m c_{ij}x_{ij}                      \\
	 & \text{subject to} &        & \sum_{j = 1}^m x_{ij} = s_i \quad \forall i \in \qty{1,\dots,n} \\
	 &                   &        & \sum_{i = 1}^m x_{ij} = d_j \quad \forall j \in \qty{1,\dots,m} \\
\end{alignat*}
which is a special case of the minimum flow problem.

\subsection{Sufficiency of transport problem}
\begin{theorem}
	Every minimum cost flow problem with either finite capacities or non-negative capacities can be translated into an equivalent transport problem.
\end{theorem}
\begin{proof}
	Consider the minimum cost flow problem on a graph \( G = (V, E) \).
	We may assume without loss of generality that \( \underline m_{ij} = 0 \) for all \( (i,j) \in E \), because we may write \( x_{ij} = \underline m_{ij} + \widetilde x_{ij} \) where \( \widetilde x_{ij} > 0 \).
	Then the conservation equation becomes
	\[
		\widetilde{b}_i + \sum_{(j,i) \in E}\widetilde{x}_{ji} = \sum_{(i,j) \in E}\widetilde{x}_{ij}
	\]
	where \( \widetilde{b}_i = \sum_{(j,i) \in E}\underline{m}_{ji} - \sum_{(i,j) \in E}\underline{m}_{ij} \).
	The regional constraints are now
	\[
		0 \leq \widetilde{x}_{ij} \leq \overline m_{ij} - \underline m_{ij}
	\]
	We assume that \( \underline m_{ij} \equiv 0 \) from now.
	If all the costs are non-negative and a particular capacity is infinite, then we can replace that capacity by a large number e.g.\ \( \sum \abs{b_i} \),
	which is the maximum amount of flow that could possibly travel along this edge.
	This transformation does not change the optimal solution.
	We have now reduced to the case where all capacities are finite.

	Now, for each such minimum cost flow problem, we will construct an equivalent transport problem that has the same feasible solutions and the same costs.
	For each vertex \( i \), we create a consumer with demand \( \sum_{(i,j) \in E} \overline m_{ik} - b_i \).
	For every edge \( (i,j) \), we create a supplier with supply \( \overline m_{ij} \).
	The total supply and the total demand are equal, since \( \sum_i b_i = 0 \).
	We now define the cost of moving from \( (i,j) \to i \) is zero.
	We further define the cost of moving from \( (i,j) \to j \) is \( c_{ij} \).

	Now, suppose \( x_{ij} \) flows from \( (i,j) \to j \).
	Then \( \overline m_{ij} - x_{ij} \) flows from \( (i,j) \to i \), since the total incoming and outgoing flow from \( (i,j) \) must balance.
	Then, since the demand at \( i \) is \( \sum_{(i,j) \in E} \overline m_{ik} - b_i \), the total flow into \( i \) satisfies
	\[
		\sum_{(i,k) \in E} (\overline m_{ik} - x_{ik}) + \sum_{(k,i) \in E} x_{ki} = \sum_{(i,j) \in E} \overline m_{ik} - b_i
	\]
	which simplifies to the conservation equation for the minimum cost flow problem.
	We can easily check that \( 0 \leq x_{ij} \leq \overline m_{ij} \).
	So this mapping between the minimum cost flow problem and the transport problem preserves feasibility of solutions.

	It now suffices to show that the costs of the two feasible solutions for the two problems are the same; since then we will have demonstrated a mapping between the two problems.
	The cost in the transport problem is \( \sum_{(i,j) \in E} x_{ij} c_{ij} \) since the edge from \( (i,j) \) to \( i \) has zero cost.
	This is identical to the cost in the minimum cost flow problem.
\end{proof}

\subsection{Optimality conditions for transport problem}
Recall that for a linear program, there are three optimality conditions: primal feasibility, dual feasibility, and complementary slackness.
These have various interpretations in the context of a transport problem.
\begin{theorem}
	If for some feasible \( x \) we have dual variables \( \bm \lambda \in \mathbb R^n \) (for suppliers) and \( \bm \mu \in \mathbb R^m \) (for consumers), such that:
	\begin{enumerate}
		\item \( \lambda_i + \mu_j \leq c_{ij} \quad \forall (i,j) \in E \); and
		\item \( (c_{ij} - (\lambda_i + \mu_j)) x_{ij} = 0 \quad \forall (i,j) \in E \)
	\end{enumerate}
	then \( x \) is an optimal solution.
\end{theorem}
\begin{proof}
	The Lagrangian of the transport problem is
	\begin{align*}
		L(x,\bm \lambda,\bm \mu) & = \sum_{i=1}^n \sum_{j=1}^m c_{ij}x_{ij} - \sum_{i=1}^n \lambda_i \qty(\sum_{j=1}^m x_{ij} - s_i) - \sum_{j=1}^m \mu_j \qty(\sum_{i=1}^n x_{ij} - d_j) \\
		                         & = \sum_{i=1}^n \sum_{j=1}^m (c_{ij} - \lambda_i - \mu_j) x_{ij} + \sum_{i=1}^n \lambda_i s_i + \sum_{j=1}^m \mu_j d_j
	\end{align*}
	\( (\bm \lambda, \bm \mu) \) is dual feasible if \( \lambda_i + \mu_j \leq c_{ij} \) for all \( i,j \).
	We have primal feasibility, dual feasibility, and complementary slackness, so optimality holds.
\end{proof}
Note that if \( \bm\lambda, \bm\mu \) are optimal, then \( \bm\lambda + k, \bm\mu - k \) are also optimal, since \( (\lambda_i + k) + (\mu_j - k) = \lambda_i + \mu_j \).
So for simplicity, we can always choose \( \lambda_1 = 0 \).
This gives \( m + n - 1 \) remaining Lagrange multipliers.
